package ex2.SearchingAndSorting.cn.edu.besti.cs1723.GK2301;

import week6.HashSearching;
import week7.LinkedBinarySearchTree;

import java.util.Arrays;

public class Searching <T extends Comparable<? super T>> {
    public static <T extends Comparable<? super T>> boolean linearSearch(T[] data, int min, int max, T target) {
        int index = min;
        boolean found = false;

        while (!found && index <= max) {
            found = data[index].equals(target);
            index++;
        }
        return found;
    }

    public static <T extends Comparable<? super T>> boolean binarySearch(T[] data, int min, int max, T target) {
        boolean found = false;
        int midpoint = (min + max) / 2;

        if (data[midpoint].compareTo(target) == 0)
            found = true;

        else if (data[midpoint].compareTo(target) > 0) {
            if (min <= midpoint - 1)
                found = binarySearch(data, min, midpoint - 1, target);
        } else if (midpoint + 1 <= max)
            found = binarySearch(data, midpoint + 1, max, target);

        return found;
    }


    //插值查找递归实现
    public static <T extends Comparable<? super T>> boolean InterpolationSearch(T[] data, int low, int high,T target) {
        boolean found = false;
            int mid = low + (high - low) * (target.compareTo(data[low])) / (data[high].compareTo(data[low]));

            if (target.compareTo(data[mid]) == 0)
                found = true;

            else if (data[mid].compareTo(target) > 0)
            {
                if (low <= mid - 1)
                    found = InterpolationSearch(data, low, mid - 1, target);
            }
            else if (mid + 1 <= high)
            {
                found = InterpolationSearch(data, mid + 1, high, target);
            }
            return found;
    }

    public static int max_size=20;//斐波那契数组的长度

    // 构造一个斐波那契数组
    public static void Fibonacci(int[] F)
    {
        F[0]=0;
        F[1]=1;
        for(int i=2;i<max_size;++i)
            F[i]=F[i-1]+F[i-2];
    }

    //斐波那契查找
    public static <T extends Comparable<? super T>> boolean FibonacciSearch(T[] data, int low, int high,T target) {

        int[] F = new int[max_size];
        Fibonacci(F); //构造一个斐波那契数组F

        int n = high - low + 1;

        int k = 0;
        while (n > F[k] - 1)  // 计算n位于斐波那契数列的位置
        {
            k++;
        }

        T[] temp;   //将数组data扩展到F[k]-1的长度
        temp = Arrays.copyOf(data, F[k] - 1);

        for (int i = n; i < F[k] - 1; ++i) {
            temp[i] = data[n - 1];
        }

        while(low <= high)
        {
            int mid = low + F[k-1] - 1;
            if(target.compareTo(temp[mid]) < 0)
            {
                high=mid-1;
                k-=1;
            }
            else if(target.compareTo(temp[mid]) > 0)
            {
                low=mid+1;
                k-=2;
            }
            else
            {
                return true;
            }
        }
        return false;
    }

    // 二叉查找树
    public boolean BinarySearchTreeSearch(T[] data, int low, int high, T target)
    {
        boolean found = false;
        LinkedBinarySearchTree linkedBinarySearchTree = new LinkedBinarySearchTree();
        // Comparable<T> comparableElement = (Comparable<T>)target;
        for (int i= low;i<= high;i++)
            linkedBinarySearchTree.addElement(data[i]);

        while (found == false&&linkedBinarySearchTree.root!=null) {
            if (target.equals(linkedBinarySearchTree.root.getElement())){
                found = true;
            }
            else
            {
                if (target.compareTo((T)linkedBinarySearchTree.root.getElement()) < 0)
                    linkedBinarySearchTree.root = linkedBinarySearchTree.root.left;
                else
                    linkedBinarySearchTree.root = linkedBinarySearchTree.root.getRight();
            }
        }
        return found;
    }

    // 分块查找
    public static <T extends Comparable<? super T>> boolean partitionSearch(T[] data, int min, int max,T target) {
        boolean found = false;
        int partition = partition(data,min,max); 
        int leftPartition = partition(data,min,partition-1);
        int rightPartition = partition(data,partition+1,max);

        if (target.compareTo(data[partition]) == 0)
            found = true;
        else
        {
            if (target.compareTo(data[partition]) < 0)
            {
                if (target.compareTo(data[leftPartition]) == 0)
                    found = true;
                else
                {
                    if (target.compareTo(data[leftPartition]) < 0)
                        found =  linearSearch(data,min,leftPartition-1,target);
                    else
                        found =  linearSearch(data,leftPartition+1,partition-1,target);
                }
            }
            else
            {
                if (target.compareTo(data[rightPartition]) == 0)
                    return true;
                else
                {
                    if (target.compareTo(data[rightPartition]) < 0)
                        found = linearSearch(data,partition+1,rightPartition-1,target);
                    else
                        found = linearSearch(data,rightPartition+1,max,target);
                }
            }
        }
        return found;
    }

    private static <T extends Comparable<? super T>> int partition(T[] data, int min, int max)
    {
        T partitionelement;
        int left, right;
        int middle = (min + max) / 2;

        //使用中间数据值作为分区元素
        partitionelement = data[middle];
        // 暂时把它移开
        swap(data, middle, min);

        left = min;
        right = max;

        while (left < right)
        {
            // 搜索一个元素，它是>分区元素
            while (left < right && data[left].compareTo(partitionelement) <= 0)
                left++;

            // 搜索一个元素，它是<分区元素
            while (data[right].compareTo(partitionelement) > 0)
                right--;

            // 交换元素
            if (left < right)
                swap(data, left, right);
        }

        // 将分区元素移动到适当的位置
        swap(data, min, right);

        return right;
    }

    private static <T extends Comparable<? super T>> void swap(T[] data, int index1, int index2)
    {
        T temp = data[index1];
        data[index1] = data[index2];
        data[index2] = temp;
    }

    // 哈希查找
    public static <T extends Comparable<? super T>> boolean hashSearch(int[] data, int target)
    {
        boolean found = false;
        HashSearching hashSearching = new HashSearching(data.length);
        hashSearching.addInAddress(data);

        if (hashSearching.search(data,target))
        {
            found = true;
        }

        return found;
    }



}
